#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

#include "main.h"

int main() {
    init();
    char cmd[30];
    strcpy(path, "/");
    cout << "[" << path << "]# ";
    while (true) {
        cin >> cmd;
        if (!strcmp(cmd, "mkdir")) {
            mkdir();
        } else if (!strcmp(cmd, "exit")) {
            exit(0);
        } else if (!strcmp(cmd, "ls")) {
            ls();
        } else if (!strcmp(cmd, "ll")) {
            ll();
        } else if (!strcmp(cmd, "cd")) {
            cd();
        } else if (!strcmp(cmd, "touch")) {
            touch();
        } else if (!strcmp(cmd, "rmdir")) {
            rmdir();
        } else if (!strcmp(cmd, "rm")) {
            rm();
        } else if (!strcmp(cmd, "free")) {
            printGroups();
        } else if (!strcmp(cmd, "super")) {
            printSuperBlock();
        } else if (!strcmp(cmd, "tree")) {
            tree(root, 0);
        } else if (!strcmp(cmd, "help")) {
            help();
        } else if (!strcmp(cmd, "block")) {
            block(root, "");
        } else {
            cout << "command not found" << endl;
        }
        cout << "[" << path << "]# ";
    }
}

void mkdir() {
    char fileName[30];
    cin >> fileName;
    FCB *tmp;
    if (isFileExist(fileName, 0) || isFileExist(fileName, 1)) {
        cout << "mkdir: cannot create directory ‘" << fileName << "’: File exists" << endl;
    } else {
        tmp = (FCB *) malloc(sizeof(FCB));
        tmp->father = present;
        strcpy(tmp->fileName, fileName);
        tmp->next = NULL;
        tmp->sub = NULL;
        tmp->type = 0;
        tmp->size = 0;
        addNode(tmp);
    }
}

void ls() {
    FCB *p;
    p = present->sub;
    if (p == NULL) {
        return;
    }
    while (p != NULL) {
        cout << p->fileName << "\t";
        p = p->next;
    }
    cout << endl;
}

void ll() {
    FCB *p;
    p = present->sub;
    if (p == NULL) {
        return;
    }
    char type[10];
    printf("%-30s%-30s%-30s\n", "文件名", "文件类型", "文件大小");
    while (p != NULL) {
        if (p->type == 0) {
            strcpy(type, "目录");
        } else {
            strcpy(type, "文件");
        }
        printf("%-28s%-28s%-28d\n", &p->fileName, type, p->size);
        p = p->next;
    }
}

void cd() {
    char dicName[30];
    cin >> dicName;

    if (present == root) {
        if (!strcmp(dicName, ".") || !strcmp(dicName, "..") || !strcmp(dicName, "/")) {
            return;
        } else if (isFileExist(dicName, 0)) {
            present = finding;
            strcat(path, finding->fileName);
        } else {
            cout << "cd: " << dicName << ": No such file or directory" << endl;
        }
    } else {
        if (!strcmp(dicName, "..")) {
            char tmp[100];
            int len1 = strlen(path);
            int len2 = strlen(present->fileName);
            strncpy(tmp, path, len1 - len2);
            tmp[len1 - len2 - 1] = '\0';
            strcpy(path, tmp);
            if (present->father == root) {
                for (int i = strlen(path) + 1; i > 0; --i) {
                    path[i] = path[i - 1];
                }
                path[0] = '/';
            }
            present = present->father;
        } else if (!strcmp(dicName, "/")) {
            present = root;
            strcpy(path, "/");
        } else if (isFileExist(dicName, 0)) {
            present = finding;
            strcat(path, "/");
            strcat(path, finding->fileName);
        } else {
            cout << "cd: " << dicName << ": No such file or directory" << endl;
        }
    }
}

void block(FCB *fcb, char pathName[]) {
    char name[100];
    strcpy(name, pathName);
    if (fcb->father != root) {
        strcat(name, "/");
        strcat(name, fcb->fileName);
    } else {
        strcat(name, fcb->fileName);
    }
    if (fcb->type == 0) {
        FCB *p = fcb->sub;
        while (p != NULL) {
            block(p, name);
            p = p->next;
        }
    } else {
        printf("%-30s", name);
        cout << "分配的盘块号: ";
        int *indexList = getIndexList(fcb);
        for (int i = 0; i < fcb->size; ++i) {
            cout << indexList[i] << " ";
        }
        cout << endl;
    }
}

void setDirect(int fileSize, vector<int> allocate, Index *index) {
    for (int i = 0; i < fileSize; ++i) {
        index->direct[i] = allocate[i];
    }
}

void setIndexOne(int fileSize, vector<int> allocate, Index *index) {
    IndexOne *indexOne = (IndexOne *) malloc(sizeof(IndexOne));
    for (int i = 0; i < LENGTH; ++i) {
        indexOne->data[i] = -1;
    }
    for (int i = 0; i < (fileSize - DIRECT_LENGTH); ++i) {
        indexOne->data[i] = allocate[i + DIRECT_LENGTH];
    }
    index->one = indexOne;
}

void setIndexTwo(int fileSize, vector<int> allocate, Index *index) {
    IndexTwo *indexTwo = (IndexTwo *) malloc(sizeof(IndexTwo));
    for (int i = 0; i < LENGTH; ++i) {
        indexTwo->one[i] = NULL;
    }

    int x = (fileSize - DIRECT_LENGTH - LENGTH) / LENGTH;
    IndexOne *indexOne;
    for (int i = 0; i < x; ++i) {
        indexOne = (IndexOne *) malloc(sizeof(IndexOne));
        for (int j = 0; j < LENGTH; ++j) {
            indexOne->data[j] = allocate[DIRECT_LENGTH + LENGTH + i * LENGTH + j];
        }
        indexTwo->one[i] = indexOne;
    }
    if ((fileSize - DIRECT_LENGTH - LENGTH) % LENGTH != 0) {
        indexOne = (IndexOne *) malloc(sizeof(IndexOne));
        for (int j = 0; j < LENGTH; ++j) {
            indexOne->data[j] = -1;
        }
        for (int i = 0; i < (fileSize - DIRECT_LENGTH - LENGTH - x * LENGTH); ++i) {
            indexOne->data[i] = allocate[DIRECT_LENGTH + LENGTH + x * LENGTH + i];
        }
        indexTwo->one[x] = indexOne;
    }
    index->two = indexTwo;
}

void setIndex(FCB *fcb, const vector<int>& allocate) {
    int fileSize = fcb->size;
    Index *index = (Index *) malloc(sizeof(Index));
    for (int i = 0; i < DIRECT_LENGTH; ++i) {
        index->direct[i] = -1;
    }
    index->one = NULL;
    index->two = NULL;
    index->three = NULL;

    if (fileSize <= DIRECT_LENGTH) {
        setDirect(fileSize, allocate, index);
    } else if (fileSize <= (DIRECT_LENGTH + LENGTH)) {
        setDirect(DIRECT_LENGTH, allocate, index);
        setIndexOne(fileSize, allocate, index);
    } else if (fileSize <= (DIRECT_LENGTH + LENGTH + LENGTH * LENGTH)) {
        setDirect(DIRECT_LENGTH, allocate, index);
        setIndexOne(DIRECT_LENGTH + LENGTH, allocate, index);
        setIndexTwo(fileSize, allocate, index);
    }
    fcb->index = index;
}

void touch() {
    char param1[30];
    char param2[30];
    char fileName[30];
    cin >> param1;
    if (!strcmp(param1, "-c")) {
        cin >> param2;
        strcpy(fileName, param2);
    } else {
        strcpy(fileName, param1);
    }
    if (remainNum == 0) {
        cout << "空闲盘块已分配完!" << endl;
        return;
    }

    if (isFileExist(fileName, 0) || isFileExist(fileName, 1)) {
        cout << "File exists" << endl;
        return;
    }

    int fileSize;
    cout << "请输入文件占用空闲块个数: ";
    cin >> fileSize;
    if (fileSize > remainNum) {
        cout << "空闲块剩余" << remainNum << "块，不足分配！" << endl;
        return;
    } else if (fileSize > DIRECT_LENGTH + LENGTH + LENGTH * LENGTH) {
        cout << "文件过大，暂不支持!" << endl;
        return;
    } else if (fileSize <= 0) {
        cout << "请输入大于0的数字！" << endl;
        return;
    }
    vector<int> allocate;
    if (!strcmp(param1, "-c")) {
        allocate =  allocateBlockContinuous(fileSize);
    } else {
        allocate = allocateBlock(fileSize);
    }
    if (allocate.empty()) {
        return;
    }
    FCB *fcb = (FCB *) malloc(sizeof(FCB));
    strcpy(fcb->fileName, fileName);
    fcb->size = fileSize;
    fcb->father = present;
    fcb->next = NULL;
    fcb->sub = NULL;
    fcb->type = 1;
    setIndex(fcb, allocate);
    addNode(fcb);
    changeFileSize(fcb, 1);

    cout << "分配的盘块号: ";
    for (int i : allocate) {
        cout << i << " ";
    }
    cout << endl;
}

void rmdir() {
    char dicName[30];
    cin >> dicName;
    if (isFileExist(dicName, 0)) {
        if (finding->sub != NULL) {
            cout << "rmdir: failed to remove ‘" << dicName << "’: Directory not empty" << endl;
        } else {
            deleteNode(finding);
        }
    } else {
        cout << "rmdir: failed to remove ‘" << dicName << "’: No such file or directory" << endl;
    }
}

int *getIndexList(FCB *fcb) {
    Index *index = fcb->index;
    int size = fcb->size, len = 0;
    int *list = (int *) malloc(sizeof(int) * size);
    if (size <= DIRECT_LENGTH) {
        int x = 0;
        while ((index->direct[x] != -1) && x < DIRECT_LENGTH) {
            list[len++] = index->direct[x];
            x++;
        }
    } else if (size <= DIRECT_LENGTH + LENGTH) {
        for (int i = 0; i < DIRECT_LENGTH; ++i) {
            list[len++] = index->direct[i];
        }
        IndexOne *indexOne = index->one;
        int x = 0;
        while ((indexOne->data[x] != -1) && x < LENGTH) {
            list[len++] = indexOne->data[x];
            x++;
        }
    } else if (size <= DIRECT_LENGTH + LENGTH + LENGTH * LENGTH) {
        for (int i = 0; i < DIRECT_LENGTH; ++i) {
            list[len++] = index->direct[i];
        }
        IndexOne *indexOne;
        indexOne = index->one;
        for (int i = 0; i < LENGTH; ++i) {
            list[len++] = indexOne->data[i];
        }
        IndexTwo *indexTwo = index->two;
        int n = (size - DIRECT_LENGTH - LENGTH) / LENGTH;
        for (int i = 0; i < n; ++i) {
            indexOne = indexTwo->one[i];
            for (int j = 0; j < LENGTH; ++j) {
                list[len++] = indexOne->data[j];
            }
        }
        if ((size - DIRECT_LENGTH - LENGTH) % LENGTH != 0) {
            indexOne = indexTwo->one[n];
            int x = 0;
            while ((indexOne->data[x] != -1) && x < LENGTH) {
                list[len++] = indexOne->data[x];
                x++;
            }
        }
    }
    return list;
}

void rm() {
    char param[30];
    char fileName[30];
    cin >> param;
    if (!strcmp(param, "-r")) {
        cin >> fileName;
        if (isFileExist(fileName, 0) || isFileExist(fileName, 1)) {
            changeFileSize(finding, -1);
            deleteNodeWithoutFree(finding);
            recursiveDelete(finding);
        }
    } else {
        if (isFileExist(param, 1)) {
            changeFileSize(finding, -1);
            releaseBlock(finding->size, getIndexList(finding));
            deleteNode(finding);
        } else if (isFileExist(param, 0)) {
            cout << "rm: cannot remove ‘" << param << "’: Is a directory";
        } else {
            cout << "rm: cannot remove ‘" << param << "’: No such file or directory" << endl;
        }
    }
}

void recursiveDelete(FCB *fcb) {
    if (fcb->type == 0) {
        FCB *p = fcb->sub;
        FCB *tmp;
        while (p != NULL) {
            tmp = p->next;
            recursiveDelete(p);
            p = tmp;
        }
        free(fcb);
    } else {
        releaseBlock(fcb->size, getIndexList(fcb));
        free(fcb);
    }
}

void help() {
    cout << "cd <目录名>\t 用于切换当前工作目录。" << endl;
    cout << "mkdir <目录名>\t 创建目录。" << endl;
    cout << "touch [-c] <文件名>\t 创建文件。-c参数为连续分配。" << endl;
    cout << "ls\t 显示当前目录下的内容。" << endl;
    cout << "ll\t 显示当前目录下的详细内容。" << endl;
    cout << "rm [-r] <文件或目录名>\t 删除一个文件或者目录。" << endl;
    cout << "rmdir <dirName>\t 删除空的目录。" << endl;
    cout << "free\t 显示空闲盘块组信息。" << endl;
    cout << "block\t 显示所有文件分配的盘块号。" << endl;
    cout << "super\t 显示超级块信息。" << endl;
    cout << "tree\t 显示系统文件树。" << endl;
    cout << "refactor\t 重构空闲盘块组。" << endl;
    cout << "exit\t 退出系统。" << endl;
    cout << endl;
}

void tree(FCB *fcb, int level) {
    for (int i = 0; i < level; ++i) {
        if (level >= 2 && i < level - 1) {
            cout << " ";
        } else {
            cout << "|-";
        }
    }
    cout << fcb->fileName << endl;
    if (fcb->type == 0) {
        FCB *p = fcb->sub;
        while (p != NULL) {
            tree(p, level + 1);
            p = p->next;
        }
    }
}

void changeFileSize(FCB *fcb, int type) {
    FCB *p = fcb->father;
    while (p != root) {
        p->size += type * fcb->size;
        p = p->father;
    }
    p->size += fcb->size;
}

void addNode(FCB *fcb) {
    FCB *p;
    if (present->sub == NULL) {
        present->sub = fcb;
    } else {
        p = present->sub;
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = fcb;
    }
}

void deleteNode(FCB *fcb) {
    deleteNodeWithoutFree(fcb);
    free(fcb);
}

void deleteNodeWithoutFree(FCB *fcb) {
    FCB *p = present->sub;
    if (p == fcb) {
        present->sub = fcb->next;
    } else {
        while (p->next != fcb) {
            p = p->next;
        }
        p->next = fcb->next;
    }
}

bool isFileExist(char fileName[], int type) {
    FCB *p;
    if (present->sub == NULL) {
        return false;
    }
    p = present->sub;
    while (p != NULL) {
        if ((!strcmp(p->fileName, fileName)) && (p->type == type)) {
            finding = p;
            return true;
        }
        p = p->next;
    }
    return false;
}

void init() {
    root = (FCB *) malloc(sizeof(FCB));
    strcpy(root->fileName, "/");
    root->type = 0;
    root->size = 0;
    root->next = NULL;
    root->father = root;
    root->sub = NULL;

    present = root;

    cout << "请输入空闲块总数:";
    cin >> blockNum;
    cout << "请输入每组的空闲块数:";
    cin >> groupSize;

    remainNum = blockNum;
    vector<int> blockList;
    blockList.reserve(blockNum);
    for (int i = 0; i < blockNum; ++i) {
        blockList.push_back(blockNum - i);
    }
    build(blockList);
    cout << "有关系统命令的详细信息，请键入 help 命令名。" << endl;
}

void buildGroup(vector<int> blockList) {
    int tmpSize = 0, endNum = 0, index = 0, size = blockList.size();
    groups.clear();
    groups.shrink_to_fit();
    //为了处理方便，把顺序倒过来，因此最后一组看做第一组
    //先构建第一组
    vector<Block> firstGroup;
    while (size > endNum && tmpSize < groupSize - 1) {
        Block block;
        block.id = blockList[index++];
        size--;
        tmpSize++;
        firstGroup.push_back(block);
    }
    groups.push_back(firstGroup);

    //构建其他组
    while (size > endNum) {
        tmpSize = 0;
        vector<Block> group;
        while (size > endNum && tmpSize < groupSize) {
            Block block;
            block.id = blockList[index++];
            size--;
            tmpSize++;
            group.push_back(block);
        }
        groups.push_back(group);
    }
}

void buildLeader() {
    //先处理第二组
    if (groups.size() >= 2) {
        groups[1][0].freeNum = groups[0].size();
        groups[1][0].free.push_back(0);
        for (int i = 0; i < groups[0].size(); ++i) {
            groups[1][0].free.push_back(groups[0][i].id);
        }
        //处理其他组
        for (int i = 2; i < groups.size(); ++i) {
            groups[i][0].freeNum = groups[i - 1].size();
            for (int j = 0; j < groups[i - 1].size(); ++j) {
                groups[i][0].free.push_back(groups[i - 1][j].id);
            }
        }
    }
}

void buildSuperBlock() {
    superBlock.free.clear();
    int n = groups.size();
    superBlock.freeNum = groups[ n - 1].size();
    if (n < 2) {
        superBlock.free.push_back(0);
    }
    for (Block &block : groups[n - 1]) {
        superBlock.free.push_back(block.id);
    }
}

void build(vector<int> blockList) {
    buildGroup(std::move(blockList));
    buildLeader();
    buildSuperBlock();
}

void printGroups() {
    if (remainNum == 0) cout << "无空闲盘块！" << endl;
    for (int i = 0; i < groups.size(); ++i) {
        cout << "第" << i + 1 << "组：" << endl << " ";
        for (Block &block : groups[i]) {//每组的每一块
            cout << block.id << " ";
        }
        cout << endl;
    }
}

void printSuperBlock() {
    int n = superBlock.free.size();
    cout << "剩余空闲盘块数：" << superBlock.freeNum << endl;
    cout << "栈深：" << n << endl;
    cout << "栈存储的盘块号：";
    for (int i = 0; i < n; i++) {//下标从1开始才是超级块的存储的块号
        cout << superBlock.free[i] << " ";
    }
    cout << endl;
}

vector<int> allocateBlock(int fileSize) {
    remainNum -= fileSize;
    int n;
    vector<int> allocate;
    Block block;
    while (fileSize--) {
        n = groups.size();
        allocate.push_back(superBlock.free.back());
        if (superBlock.freeNum == 1 && superBlock.free[0] != 0) {
            block = groups[n - 1][0];
            copyToSuperBlock(block);
            block.free.clear();
            block.free.shrink_to_fit();
            groups.pop_back();
            groups.shrink_to_fit();
        } else {
            superBlock.freeNum--;
            superBlock.free.pop_back();
            groups[n - 1].pop_back();
        }
    }
    if (remainNum == 0) {
        groups.pop_back();
        groups.shrink_to_fit();
    }
    return allocate;
}

vector<int> allocateBlockContinuous(int fileSize) {
    remainNum -= fileSize;
    refactor();
    int n, a = 0, tmpSize = fileSize;
    vector<int> allocate, list;
    Block block;
    while (tmpSize--) {
        a++;
        if (a > 1) {
            if (superBlock.free.back()-allocate.back() > 1) {
                a = 0;
                tmpSize = fileSize;
                for (int i = 0; i < allocate.size(); ++i) {
                    list.push_back(allocate[i]);
                }
                allocate.clear();
                continue;
            }
        }
        allocate.push_back(superBlock.free.back());
        n = groups.size();
        if (superBlock.freeNum == 1 && superBlock.free[0] != 0) {
            block = groups[n - 1][0];
            copyToSuperBlock(block);
            block.free.clear();
            block.free.shrink_to_fit();
            groups.pop_back();
            groups.shrink_to_fit();
        } else if (superBlock.freeNum != 1) {
            superBlock.freeNum--;
            superBlock.free.pop_back();
            groups[n - 1].pop_back();
        } else {
            superBlock.free.pop_back();
            superBlock.freeNum--;
            groups[n - 1].pop_back();
            if (tmpSize > 0) {
                cout << "无法分配连续的存储空间！" << endl;
                for (int i = 0; i < allocate.size(); ++i) {
                    list.push_back(allocate[i]);
                }
                allocate.clear();
                allocate.shrink_to_fit();
                int  *blockList = (int *) malloc(sizeof(int) * list.size());
                for (int i = 0; i < list.size(); ++i) {
                    blockList[i] = list[i];
                }
                groups.pop_back();
                groups.shrink_to_fit();
                releaseBlock(list.size(), blockList);

                return allocate;
            }
        }
    }

    int  *blockList = (int *) malloc(sizeof(int) * list.size());
    for (int i = 0; i < list.size(); ++i) {
        blockList[i] = list[i];
    }
    releaseBlock(list.size(), blockList);

    if (remainNum == 0) {
        groups.pop_back();
        groups.shrink_to_fit();
    }
    return allocate;
}

void copyToSuperBlock(Block &block) {
    superBlock.free.clear();
    superBlock.freeNum = block.freeNum;
    for (int id : block.free) {
        superBlock.free.push_back(id);
    }
}

void releaseBlock(int size, int *blockList) {
    for (int i = size - 1; i >= 0; --i) {
        Block block;
        block.id = blockList[i];
        if (superBlock.free.size() == groupSize) {
            vector<Block> newGroup;
            copyToBlock(block);
            newGroup.push_back(block);
            groups.push_back(newGroup);
        } else {
            if (groups.size() == 0) {
                vector<Block> newGroup;
                groups.push_back(newGroup);
            }
            groups[groups.size() - 1].push_back(block);
            superBlock.free.push_back(block.id);
            superBlock.freeNum++;
        }
    }
    remainNum += size;
}

void copyToBlock(Block &block) {
    block.freeNum = superBlock.freeNum;
    for (int id : superBlock.free) {
        block.free.push_back(id);
    }
    superBlock.free.clear();
    superBlock.freeNum = 1;
    superBlock.free.push_back(block.id);
}

void refactor() {
    vector<int> list;
    for (vector<Block> &group : groups) {
        for (Block block : group) {
            list.push_back(block.id);
        }
    }
    sort(list.begin(), list.end(), cmp);
    build(list);
}

bool cmp(int a, int b) {
    return a > b;
}
